Languguage OS 2/Languguage OS II Version 10-94 (Knowledge Media)(1994).ISO/language/asa/readme

Text File | 1994-10-23 | 93KB | 2,773 lines

             ADAPTIVE SIMULATED ANNEALING (ASA) (C)



                          Lester Ingber

                     Lester Ingber Research
                          P.O. Box 857
                        McLean, VA 22101

                    [e-mail]




















































Adaptive Simulated Annealing (ASA)                  Lester Ingber


1.  GNU General Public License (GPL)

     This  Adaptive  Simulated Annealing (ASA) code is being made
available under a GNU COPYING "copyleft" license, and is owned by
Lester Ingber[1].  Please read the copy of this license contained
in this directory.  Its intent is  to  make  this  code  publicly
available  to the widest audience while maintaining the integrity
of the basic algorithm.

2.  Documentation


2.1.  Table of Contents

     A Table of Contents of the  three  levels  of  headers  with
their  page numbers is located at the end of this document.  This
may be placed after the first title page, or left at the end  for
quick reference.

2.2.  readme.ms

     The  readme.ms  file  is used to prepare other documentation
files using UNIX(R) MS macros.

2.3.  README and README+

     README is an ASCII file that can be previewed on your screen
or sent to an ASCII lineprinter.

     README+   is   README  without  any  filters  to  strip  off
underlining and bold enhancements.  This is uuencoded to the file
README+.uu  in  order  to  pass through the shar utility.  If you
have  downloaded  ASA-shar  or  ASA-shar.Z,  to  use  this  file,
`uudecode README+.uu` will leave README+.

2.4.  asa.[13nl] Manpage

     The  README  or  README+  file can be copied to a file named
asa.[l3], and asa.[13] can be installed as MANPATH/cat1/asa.1  or
MANPATH/cat3/asa.3, where MANPATH is the place your man directory
is located.  If you do not have any cat[13] directories  on  your
system,   then   installing  a  copy  of  README  or  README+  as
MANPATH/man[13nl]/asa.[13nl], choosing one  of  the  suffixes  in
[13nl]  for  your  choice  of directory and asa file name, should
work fine on most machines.  (However, passing  asa.[13nl]  which
is  the  equivalent  of  README[+] through man may strip out some
items like \"asa_out\".)   You  likely  can  avoid  some  further
undesirable  formatting by man by placing '.nf' on the first line
of this file.

2.5.  README.ps

     README.ps is a PostScript(R) formatted  file  which  may  be
previewed  on  your screen if you have the proper software, or it



                              - 1 -





Adaptive Simulated Annealing (ASA)                  Lester Ingber


may be sent to a PostScript(R) printer to produce hardcopy.

2.6.  Additional Documentation

     CHANGES is a terse record of major changes made in  the  ASA
code.    NOTES  is  a  collection  of  recommended  enhancements,
modifications,  comments,  caveats,  etc.,  that  might   be   of
interest.

     The file asa_new in ftp.alumni.caltech.edu: /pub/ingber is a
list of major changes in ASA since the last announcement  to  the
ASA_list.   This can be used as a quick guide to determine if you
should download the latest ASA code in  the  archive  before  the
next announcement.

     An   addendum   to   NOTES   is   the   file  asa_papers  in
ftp.alumni.caltech.edu:  /pub/ingber,  listing  some  (p)reprints
that  have  used  ASA  or its precursor VFSR.  This separation of
information is to minimize updating versions of the ASA directory
due to changes in this section.

     It  is  certain  that  there  is much research to be done on
determining optimal or even reasonable ASA parameters, e.g.,  the
set  of  Program  Options,  for  different  classes  of  systems,
especially in higher dimensional spaces of user parameters.   (In
the  NOTES  file  are  some  comments  on  how  you might use ASA
recursively to determine the optimal set of some Program  Options
for  a  given  system.)   A  major  purpose  of  making this code
publicly available is to motivate more of this research, and thus
make the code more useful to a wider audience.

2.7.  Parallelizing ASA and PATHINT Project (PAPP)

     The  file  /pub/ingber/MISC.DIR/parallel.txt   contains   an
update  of  the Parallelizing ASA and PATHINT Project (PAPP).  No
code will be released until it has passed some  reasonable  tests
and has reasonable documentation.

2.8.  Additional Information

     Sorry, I cannot assume the task of mailing out hardcopies of
code or papers.   My volunteer time assisting people  with  their
queries on my codes and papers must be limited to electronic mail
correspondence.  Commercial consulting appointments can  be  made
by contacting me via e-mail, mail, or calling 1.800.L.INGBER.

3.  Availability of ASA Code


3.1.  Caltech

     The  latest Adaptive Simulated Annealing (ASA) code and some
related (p)reprints can  be  retrieved  via  anonymous  ftp  from
ftp.alumni.caltech.edu   [131.215.139.234]   in  the  /pub/ingber



                              - 2 -





Adaptive Simulated Annealing (ASA)                  Lester Ingber


directory.  This archive  also  can  be  accessed  via  WWW  path
http://alumni.caltech.edu/~ingber/                             or
ftp://ftp.alumni.caltech.edu/pub/ingber/.

     Interactively [brackets signify machine prompts]:
        [your_machine%] ftp ftp.alumni.caltech.edu
        [Name (...):] anonymous
        [Password:] your_e-mail_address
        [ftp>] cd pub/ingber
        [ftp>] binary
        [ftp>] ls
        [ftp>] get file_of_interest
        [ftp>] quit
The 00index file  contains  an  index  of  the  other  files  and
information  on  getting  gzip  and  unshar  for  DOS(R), MAC(R),
UNIX(R), and VMS(R) systems.

     The latest version of ASA, ASA-x.y  (x  and  y  are  version
numbers),  can  be  obtained in several formats.  ASA-shar.Z is a
compress'd shar'd file of the current code.  For the  convenience
of  users who do not have any uncompress/gunzip utility, there is
a file ASA-shar which is an uncompress'd copy of  ASA-shar.Z;  if
you do not have sh or shar, you still can delete the first-column
X's and separate the files at the END_OF_FILE  locations.   There
are  tar'd  versions  in  compress and gzip format, ASA.tar.Z and
ASA.tar.gz, respectively.  There also is a current zip'd version,
ASA.zip, in which all files have been processed through unix2dos.
Directory /pub/ingber/0lower.dir contains links  to  these  files
for some PC users who may have difficulty with upper case.

     Patches ASA-diff-x1.y1-x2.y2.Z up to the present version can
be prepared, if a good case for doing so is presented.  These may
be  concatenated  as  required before applying.  If you require a
specific patch that is not  contained  in  the  archive,  contact
[e-mail].

3.2.  Electronic Mail

     If  you  do  not  have  ftp  access,  get information on the
FTPmail service by: mail [e-mail],  and  send  only
the word "help" as the body of the message.  You will receive the
information  in  /pub/ingber/UTILS.DIR/ftpmail.txt.    Similarly,
from a BITNET site, send the word "help" as the body of a message
to bitftp@pucc ([e-mail] if from an Internet site).

     If any of the above are not possible, and if your mailer can
handle  large  files (please test this first), the code or papers
you require can  be  sent  as  uuencode'd  compress'd  files  via
electronic  mail.   If you have gzip, resulting in smaller files,
please state this.







                              - 3 -





Adaptive Simulated Annealing (ASA)                  Lester Ingber


3.3.  ASA Mailing List

     If you wish to be placed on the electronic mailing  ASA_list
to  receive  major  updates  between  public announcements of new
versions,  please   send   e-mail   stating   this   request   to
[e-mail].   Update  notices are sent to the
ASA_list about every month or two, more frequently if  warranted,
e.g., in cases of important bug fixes; these notices are the only
e-mail sent to the ASA_list.  This is highly recommended  if  you
plan  to use ASA on complex systems, as there is ongoing research
using and testing ASA by many users.  To  unsubscribe  from  this
list,  simply  send  an  electronic  mail  with  this  request to
[e-mail].

4.  Background


4.1.  Context

     The ASA code was  first  developed  in  1987  as  Very  Fast
Simulated  Reannealing  (VFSR)  to  deal  with  the  necessity of
performing adaptive global optimization on multivariate nonlinear
stochastic  systems[2].   VFSR was recoded and applied to several
complex  systems,  in   combat   analysis[3],   finance[4],   and
neuroscience[5].   The first applications to combat analysis used
code  written  in  RATFOR  and  converted  into  FORTRAN.   Other
applications  since  then  have used new code written in C.  (The
NOTES file contains some comments on interfacing ASA with FORTRAN
codes.)  A paper has indicated how this technique can be enhanced
by combining it with some other  powerful  algorithms,  e.g.,  to
produce  an  algorithm  for parallel computation[6].  In November
1992, the VFSR C-code was rewritten, e.g., changing to the use of
long  descriptive  names,  and made publicly available as version
6.35 under the same GNU license as this ASA code[7].

     Beginning  in  January  93,  many  adaptive  features   were
developed,  largely  in  response  to users' requests, leading to
this ASA code.  ASA has been examined in the context of a  review
of   methods   of  simulated  annealing  using  annealing  versus
quenching (faster temperature schedules than permitted  by  basic
heuristic  proof  of  ergodicity)[8].  ASA is now used world-wide
across many disciplines[9].

4.2.  Outline of ASA Algorithm

     Details of the ASA algorithm  are  best  obtained  from  the
published  papers.  There are three parts to its basic structure.

4.2.1.  Generating Probability Density Function

     In  a  D-dimensional  parameter  space  with  parameters p^i
having ranges [A_i, B_i], about the k'th last saved point (e.g, a
local   optima),   p_k^i,  a  new  point  is  generated  using  a
distribution defined by the product  of  distributions  for  each



                              - 4 -





Adaptive Simulated Annealing (ASA)                  Lester Ingber


parameter,  g^i(y^i;  T_i),  in  terms of random variables y^i in
[-1,  1],  where  p_k+1^i  =  p_k^i  +  y^i(B_i   -   A_i),   and
"temperatures" T_i,
        g^i(y^i; T_i) = 1/[2(|y^i| + T_i)(1 + 1/T_i)].

4.2.2.  Acceptance Probability Density Function

     The cost functions, C(p_k+1) - C(p_k), are compared using  a
uniform random generator, U in [0, 1), in a "Boltzmann" test: If
        exp[-(C(p_k+1) - C(p_k))/T_cost] > U,
where  T_cost  is  the "temperature" used for this test, then the
new point is accepted  as  the  new  saved  point  for  the  next
iteration.  Otherwise, the last saved point is retained.

4.2.3.  Reannealing Temperature Schedule

     The  annealing schedule for each parameter temperature, T_i,
from a starting temperature T_i0, is
        T_i(k_i) = T_0i exp(-c_i k_i^(1/D)).
This is discussed further below.

     The annealing schedule for the cost temperature is developed
similarly  to the parameter temperatures.  However, the index for
reannealing the cost  function,  k_cost,  is  determined  by  the
number  of  accepted  points,  instead of the number of generated
points as used for the parameters.  This choice was made  because
the   Boltzmann   acceptance   criteria   uses   an   exponential
distribution which is not as fat-tailed as the  ASA  distribution
used  for  the  parameters.   This schedule can be modified using
several OPTIONS.  In particular, the  Pre-Compile  DEFINE_OPTIONS
USER_COST_SCHEDULE    permits    quite    arbitrary    functional
modifications for this annealing schedule.

     As determined by the Program Options selected, the parameter
"temperatures"  may  be  periodically  adaptively  reannealed, or
increased relative to their previous values, using their relative
first derivatives with respect to the cost function, to guide the
search "fairly" among the parameters.

4.3.  Efficiency Versus Necessity

     ASA is not necessarily an "efficient" code.  For example, if
you  know  that  your  cost function to be optimized is something
close to a parabola, then a simple gradient Newton search  method
most  likely  would  be  faster  than ASA.  ASA is believed to be
faster and more robust than other simulated annealing  techniques
for  most  complex problems with multiple local optima; again, be
careful to note that some problems  are  best  treated  by  other
algorithms.   If you do not know much about the structure of your
system, and especially if it has  complex  constraints,  and  you
need  to  search  for  a  global  optimum,  then this ASA code is
heartily recommended to you.





                              - 5 -





Adaptive Simulated Annealing (ASA)                  Lester Ingber


5.  Outline of Use

     Set up the ASA interface: Your  program  should  be  divided
into   two  basic  modules.   (1)  The  user  calling  procedure,
containing the cost function to be minimized (or its negative  if
you  require  a  global maximum), here is contained in user.c and
user.h.  (2) The ASA optimization procedure, here is contained in
asa.c  and  asa.h.   The file asa_user.h contains definitions and
macros common to both asa.h and user.h.  Furthermore,  there  are
some  options to explore/read below.  It is assumed there will be
no confusion over the standard uses of the  term  "parameter"  in
different contexts, e.g., as an element passed by a subroutine or
as a physical coefficient in a cost function.

     ASA has been run successfully on many  machines  under  many
compilers.   To check out your own system, you can run `make` (or
the equivalent set of commands in the Makefile), and compare your
asa_out  and  user_out  files to the test_asa and test_usr files,
respectively,  provided  with  this  code.   (For   these   runs,
TIME_CALC=TRUE,  discussed  below,  was  added to the compilation
options.)  No attempt was made to optimize any compiler, so  that
the  test  runs do not really signify any testing of compilers or
architectures; rather they are meant to be used  as  a  guide  to
determine what you might expect on your own machine.

     The   major   sections   below   describe   the  compilation
procedures, the Program Options available to you to  control  the
code,  the  use  of  templates  to  set  up  your user module and
interface to the asa module, and how to submit bug reports.

     If you already have your own cost  function  defined,  as  a
quick guide to get started, you can search through user.c for all
occurrences of "MY_COST"  to  insert  the  necessary  definitions
required to run ASA.

6.  Makefile/Compilation Procedures

     The  PostScript(R)  README.ps  and  ASCII README and README+
files were generated using `make doc'.   The  Makefile  describes
some  options for formatting these files differently.  Use `make'
or `make all' to compile and run asa_run, the executable prepared
for  the  test  function.   Examine the Makefile to determine the
"clean" options available.

     Since complex problems  by  their  nature  are  often  quite
unique, it is unlikely that the default parameters are just right
for your problem.  However, experience has shown that  if  you  a
priori  do  not have any reason to determine your own parameters,
then you might do just fine using these defaults, and  these  are
recommended  as  a  first-order  guess.   These  defaults  can be
changed simply by  adding  to  the  DEFINE_OPTIONS  line  in  the
Makefile,  by  passing  options  on  your  command  line,  and by
changing  structure  elements  in  the  user  or  asa  module  as
described  below.   Depending  on how you integrate ASA into your



                              - 6 -





Adaptive Simulated Annealing (ASA)                  Lester Ingber


own user modules, you may wish to  modify  this  Makefile  or  at
least   use  some  of  these  options  in  your  own  compilation
procedures.

     Note  that  the  Makefile  is  just  a  convenience,  not  a
necessity,  to  use  ASA.   E.g., on systems which do not support
this utility, you may simply  compile  the  files  following  the
guidelines  in  the  Makefile,  taking  care  to pass the correct
DEFINE_OPTIONS to your compilation commands at your shell prompt.
Still  another  way,  albeit  not  as  convenient, is to make the
desired changes in the asa_user.h, and asa.h or user.h  files  as
required.

     Since   the   Makefile   contains   comments   giving  short
descriptions of some options,  it  should  be  considered  as  an
extension  of  this documentation file.  For convenience, most of
this information is repeated below.  However, to see how they can
be used in compilations, please read through the Makefile.

     For  example,  to  run  the  ASA  test problem using the gcc
compiler, you could just type at your "%" prompt:
        % gcc -g -DASA_TEST=TRUE -o asa_run user.c asa.c -lm
        % asa_run
You may have to feed different options to your own compiler.  The
resulting  asa_out file should only differ from the test_asa file
by having different values for  the  OPTIONS_FILE  and  TIME_CALC
lines, and by not having a few lines marking the CPU time.

     If  you  have  defined  your  own  cost  function within the
"MY_COST" guides in user.c, then ASA_TEST should be set to  FALSE
(the default if ASA_TEST is not defined in your compilation lines
or in the Makefile).  The code for ASA_TEST=TRUE  is  given  just
above  these  guides  as  a  template  to  use  for your own cost
function.

7.  User Options

     The DEFINE_OPTIONS  are  organized  into  two  groups:  Pre-
Compile Options and (Pre-Compile) Printing Options.  In addition,
there are some alternatives to explore under Compiler Choices and
Document  Formatting.   Below  are  the DEFINE_OPTIONS with their
defaults.  The Program Options are  further  discussed  in  other
sections in this document.

7.1.  Pre-Compile DEFINE_OPTIONS


7.1.1.  OPTIONS_FILE=TRUE

     You can elect to read in the Program Options from asa_opt by
setting OPTIONS_FILE=TRUE.  OPTIONS_FILE=TRUE can be set  in  the
Makefile in compilation commands or in asa_user.h.





                              - 7 -





Adaptive Simulated Annealing (ASA)                  Lester Ingber


7.1.2.  ASA_LIB=FALSE

     Setting ASA_LIB=TRUE will facilitate your running asa() as a
library call from another program, calling asa_main() in  user.c.
In  the templates provided, all initializations and cost function
definitions are set up in user.c.  For example, you may  wish  to
have  some  data  read in to a module that calls asa_main(), then
parses out this information  to  the  arrays  in  asa_main()  and
initialize_parameters (and possibly recur_initialize_parameters).
In conjunction with setting printout to stdout (see  ASA_OUT  and
USER_ASA_OUT),  this  can  be  a convenient way of using the same
asa_run executable for many runs.

7.1.3.  HAVE_ANSI=TRUE

     Setting HAVE_ANSI=FALSE will permit you to use an older  K&R
C  compiler.   This option can be used if you do not have an ANSI
compiler, overriding the  default  HAVE_ANSI=TRUE.   If  you  use
HAVE_ANSI=FALSE,  change  CC  and CDEBUGFLAGS as described in the
Makefile.

7.1.4.  IO_PROTOTYPES=TRUE

     Some machines do not like any other  I/O  prototyping  other
than  those in their own include files, e.g., like one Convex-120
that was tested.  Other machines, like a  Dec-3100  under  Ultrix
complained that the ANSI I/O prototypes were inconsistent.  A Sun
under gcc gave  warnings  if  no  I/O  prototypes  were  present.
Therefore,  the  defaults in asa_user.h use K&R system prototypes
even for the ANSI compiler,  for  fprintf,  fflush,  fclose,  and
exit, and for fscanf in user.h.  Setting IO_PROTOTYPES=FALSE will
comment out even these declarations.  This also has worked on  an
Indigo and on a Cray C90/UNICOS 8.0.

7.1.5.  TIME_CALC=FALSE

     Some  systems  do not have the time include files used here;
others have different scales for  time.   Setting  TIME_CALC=TRUE
will  permit  use  of  the  time routines.  In the NOTES are some
contributed code  that  should  be  useful  for  some  particular
systems.

7.1.6.  TIME_STD=FALSE

     Some  systems, e.g., hpux, use other Unix-standard macros to
access time.  Setting  TIME_STD=TRUE  when  using  TIME_CALC=TRUE
will use these time routines instead.

7.1.7.  INT_LONG=TRUE

     Some smaller systems choke on `long int' and this option can
be set to INT_LONG=FALSE to turn off warnings and  possibly  some
errors.   The cast LONG_INT is used to define `int' or `long int'
appropriately.



                              - 8 -





Adaptive Simulated Annealing (ASA)                  Lester Ingber


7.1.8.  INT_ALLOC=FALSE

     The cast on *number_parameters is  set  to  ALLOC_INT  which
defaults  to LONG_INT.  On some machines, ALLOC_INT might have to
be set to int  if  there  is  a  strict  requirement  to  use  an
(unsigned) int for calloc, while `long int' still can be used for
other aspects of ASA.  If ALLOC_INT is to  be  set  to  int,  set
INT_ALLOC to TRUE.

7.1.9.  SMALL_FLOAT=1.0E-18

     SMALL_FLOAT  is  a  measure of accuracy permitted in log and
divide operations in asa, i.e., which is not precisely equivalent
to  a  given  machine's  precision.   There  also are Pre-Compile
DEFINE_OPTIONS  to  separately  set  constants  for  minimum  and
maximum doubles and precision permitted by your machine.  Experts
who  require  the  very  best  precision  can   fine-tune   these
parameters in the code.

     Such  issues  arise  because the fat tail of ASA, associated
with high parameter temperatures, is very important for searching
the  breadth  of  the  ranges especially in the initial stages of
search.  However, the parameter temperatures require small values
at  the  final  stages  of  the  search  to  converge to the best
solution,  albeit  this  is  reached  very  quickly   given   the
exponential  schedule proven in the referenced publications to be
permissible with ASA.  Note that the test problem in user.c is  a
particularly  nasty one, with 1E20 local minima and requiring ASA
to search over 12 orders of magnitude of the cost function before
correctly  finding the global minimum.  Thus, intermediate values
disagree somewhat for SMALL_FLOAT=1.0E-12 from the settings using
SMALL_FLOAT=1.0E-18     (the    default);     they    agree    if
SMALL_FLOAT=1.0E-12 while also setting  MIN_DOUBLE=1.0E-18.   The
results  diverge  when the parameter temperatures get down to the
range of E-12, limiting the accuracy of  the  SMALL_FLOAT=1.0E-12
run.

7.1.10.  MIN_DOUBLE=SMALL_FLOAT

     You  can  define  your own machine's minimum positive double
here if you know it.

7.1.11.  MAX_DOUBLE=1.0/SMALL_FLOAT

     You can define your own machine's maximum double here if you
know it.

7.1.12.  EPS_DOUBLE=SMALL_FLOAT

     You  can define your own machine's maximum precision here if
you know it.






                              - 9 -





Adaptive Simulated Annealing (ASA)                  Lester Ingber


7.1.13.  NO_PARAM_TEMP_TEST=FALSE

     If NO_PARAM_TEMP_TEST is set to  TRUE,  then  all  parameter
temperatures  less  than EPS_DOUBLE are set to EPS_DOUBLE, and no
exit is called.

7.1.14.  NO_COST_TEMP_TEST=FALSE

     If NO_COST_TEMP_TEST is set to TRUE, then a cost temperature
less than EPS_DOUBLE is set to EPS_DOUBLE, and no exit is called.

7.1.15.  SELF_OPTIMIZE=FALSE

     The user module contains a template to  illustrate  how  ASA
may  be  used  to self-optimize its Program Options.  This can be
very CPU-expensive and is of course dependent on how  you  define
your  recursive  cost  function  (recur_cost_function in the user
module).  The example given returns from recur_cost_function  the
number  of  function  evaluations  taken to optimization the test
cost_function, with the constraint to only  accept  optimizations
of  the  cost_function  that are lower than a specified value.  A
few lines of code can be uncommented in user.c to  force  a  fast
exit  for  this  demo;  search  for FAST EXIT.  This example uses
OPTIONS_FILE=FALSE (the default) in the Pre-Compile Options; note
that  OPTIONS_FILE=TRUE  here  would  set  Program  Options  from
asa_opt for the top level program, not for  the  Program  Options
for the cost_function().

     This  can be useful when approaching a new system, and it is
suspected that the default ASA Program Options  are  not  at  all
efficient  for  this system.  It is suggested that a trimmed cost
function or data set be used to get a reasonable guess for a good
set  of  Program Options.  ASA has demonstrated that it typically
is quite robust under a given set of Program Options, so it might
not  make  too  much  sense to spend lots of resources performing
additional fine  tuning  of  the  these  options.   Also,  it  is
possible you might crash the code by permitting ranges of Program
Options  that  cause  your  particular  cost_function  to  return
garbage to asa().

7.1.16.  ASA_TEST=FALSE

     Setting  ASA_TEST  to  TRUE will permit running the ASA test
problem.  This has  been  added  to  the  DEFINE_OPTIONS  in  the
Makefile  so that just running make will run the test problem for
the new user.

     Searching user.c for "MY_COST" provides a guide to the  user
for  additional  code  to add for his/her own system.  Just above
each occurrence of these guides is  the  corresponding  code  for
ASA_TEST=TRUE.   Keeping  the  default  of  ASA_TEST set to FALSE
permits such changes without overwriting the test example.





                              - 10 -





Adaptive Simulated Annealing (ASA)                  Lester Ingber


7.1.17.  ASA_TEMPLATE=FALSE

     There are several templates that come  with  the  ASA  code,
used  to  test  several  OPTIONS.  To permit use of these OPTIONS
without having to delete these extra tests, these  templates  are
wrapped  with  ASA_TEMPLATE.   To use tests associated with these
OPTIONS, which can be determined by reading the  code,  just  set
ASA_TEMPLATE  to  TRUE  in  the  Makefile  or in your compilation
procedures.

     Note that running the ASA test  problem  in  user.c  is  not
affected  by  ASA_TEMPLATE.   To  use your own cost function, you
must at least rewrite relevant portions  of  cost_function()  and
initialize_parameters() in user.c.

7.1.18.  OPTIONAL_DATA=FALSE

     It  can  be  useful  to return additional information to the
user module from the asa module.  When OPTIONAL_DATA  is  set  to
true,  an  additional  Program  Option  pointer,  *asa_data,   is
available in USER_DEFINES *OPTIONS to gather such data.

     In one ASA_TEMPLATE provided (see the set of  DEFINE_OPTIONS
used  in  the  Makefile),  OPTIONAL_DATA  is  used  together with
SELF_OPTIMIZE to find  the  set  of  ASA  parameters  giving  the
(statistically)  smallest number of generated points to solve the
ASA test problem, assuming  this  were  run  several  times  with
different  random  seeds  for  randflt  in user.c (e.g., changing
"seed" in myrand).  Here, asa_data[0] is used as a flag to  print
out asa_data[1] in user.c, set to *best_number_generated_saved in
asa.c.

7.1.19.  USER_COST_SCHEDULE=FALSE

     The function used to control the  cost_function  temperature
schedule  is  of the form test_temperature in asa.c.  If the user
sets the Pre-Compile DEFINE_OPTIONS USER_COST_SCHEDULE  to  TRUE,
then   this  function  of  test_temperature  can  be  controlled,
adaptively if desired,  in  user.c  in  cost_schedule()  (and  in
recur_cost_schedule()   if  SELF_OPTIMIZE  is  TRUE)  by  setting
USER_COST_SCHEDULE to TRUE.  The names of these functions are set
to the relevant pointer in user.c, and can be changed if desired,
i.e.,
   USER_OPTIONS->cost_schedule = user_cost_schedule;
   RECUR_USER_OPTIONS->cost_schedule = recur_user_cost_schedule;

7.1.20.  USER_REANNEAL_FUNCTION=FALSE

     In asa.h, the macro
   #define \
           REANNEAL_FUNCTION(temperature, tangent, max_tangent) \
              (temperature * (max_tangent / tangent))
is used to determine the  new  temperature,  subject  to  further
tests    in    reanneal().     This    is    the    default    if



                              - 11 -





Adaptive Simulated Annealing (ASA)                  Lester Ingber


USER_REANNEAL_FUNCTION is FALSE.

     If   the   user   sets   the   Pre-Compile    DEFINE_OPTIONS
USER_REANNEAL_FUNCTION to TRUE, then the function controlling the
new reannealed  temperature  can  be  controlled,  adaptively  if
desired  using USER_OPTIONS, in user.c in user_reanneal(), and in
recur_user_reanneal() if SELF_OPTIMIZE is  TRUE.   The  names  of
these  functions  are  set to the relevant pointer in user.c, and
can be changed if desired, i.e.,
   USER_OPTIONS->reanneal_function = user_reanneal;
   RECUR_USER_OPTIONS->reanneal_function = recur_user_reanneal;

7.1.21.  ASA_SAMPLE=FALSE

     When ASA_SAMPLE is set to TRUE, data  is  collected  by  ASA
during  its  global optimization process to importance-sample the
user's variables.  Five OPTIONS become available to  monitor  the
sampling:     n_accepted,    bias_acceptance,    *bias_generated,
average_weights, and limit_weights.

     If   average_weights   exceeds   the   user's   choice    of
limit_weights,  then  the  ASA_OUT  file  will contain additional
detailed information, including temperatures and biases for  each
current  parameter.   To facilitate extracting importance-sampled
information from the file printed out  by  the  asa  module,  all
relevant lines start with :SAMPLE[ |:|#|+].

     Many  Monte  Carlo  sampling  techniques require the user to
guess an appropriately decreasing "window" to sample the variable
space.   The  fat  tail  of  the ASA generating function, and the
decreasing effective range of newly  accepted  points  driven  by
exponentially  decreasing  temperature  schedules,  removes  this
arbitrary aspect of such sampling.

     However, note that, albeit local  optima  are  sampled,  the
efficiency  of ASA optimization most often leads to poor sampling
in regions whose cost function is far  from  the  optimal  point;
many  such  points  may  be important contributions to algorithms
like integrals.  Accordingly, ASA_SAMPLE likely is best  used  to
explore new regions and new systems.

     To  increase  the  sampling  rate  and  thereby  to possibly
increase the accuracy of this algorithm, use one or a combination
of  the  various OPTIONS available for slowing down the annealing
performed by ASA.

7.1.22.  ASA_PARALLEL=FALSE

     When  ASA_PARALLEL  is  set  to  TRUE,  parallel  blocks  of
generated states are calculated of number equal to the minimum of
OPTIONS->gener_block  and  OPTIONS->gener_block_max.   For   most
systems  with  complex  nonlinear cost functions that require the
fat tail of the ASA distribution, leading to  high  generated  to
acceptance  ratios,  this  is  the most CPU intensive part of ASA



                              - 12 -





Adaptive Simulated Annealing (ASA)                  Lester Ingber


that can benefit from parallelization.

     The actual number  calculated  is  determined  by  a  moving
average,  determined  by  OPTIONS->gener_mov_avr, of the previous
numbers of OPTIONS->gener_block of generated states  required  to
find    a    new    best    accepted    state.    If   and   when
OPTIONS->gener_mov_avr is set to 0, then OPTIONS->gener_block  is
not changed thereafter.

7.2.  Printing DEFINE_OPTIONS


7.2.1.  ASA_PRINT=TRUE

     Setting this to FALSE will suppress all printing within asa.

7.2.2.  ASA_OUT=\"asa_out\"

     The name of the output file  containing  all  printing  from
asa.    If   you   wish   to   attach   a   process   number  use
ASA_OUT=\"asa_out_$$\".  (Use ASA_OUT=\"asa_out_$$$$\" if this is
set  in  the Makefile.) If ASA_OUT=\"STDOUT\" then ASA will print
to stdout.

7.2.3.  USER_ASA_OUT=FALSE

     When USER_ASA_OUT is set  to  TRUE,  an  additional  Program
Option  pointer,  *asa_out_file,  is  used to dynamically set the
name(s) of the file(s) printed out  by  the  asa  module.   (This
overrides    any    ASA_OUT    settings.)     In    user.c,    if
USER_OPTIONS->asa_out_file = "STDOUT";, then ASA  will  print  to
stdout.

     In  one ASA_TEMPLATE provided (see the set of DEFINE_OPTIONS
used in the Makefile), USER_ASA_OUT is used to generate  multiple
files  of separate ASA runs.  (If USER_OPTIONS->QUENCH_PARAMETERS
and/or USER_OPTIONS->QUENCH_COST is set to TRUE in  user.c,  then
this  ASA_TEMPLATE  will  separate  runs with different quenching
values.)

7.2.4.  ASA_PRINT_INTERMED=TRUE

     This option is only effective if ASA_PRINT is TRUE.  Setting
ASA_PRINT_INTERMED  to  FALSE  will  suppress  much  intermediate
printing within asa, especially arrays which can  be  large  when
the  number  of  parameters  is  large.  Printing at intermediate
stages  of  testing/reannealing  has   been   turned   off   when
SELF_OPTIMIZE  is  set to TRUE, since there likely can be quite a
bit of data generated; this can be changed by explicitly  setting
ASA_PRINT_INTERMED to TRUE in the Makefile or on your compilation
command lines.






                              - 13 -





Adaptive Simulated Annealing (ASA)                  Lester Ingber


7.2.5.  ASA_PRINT_MORE=FALSE

     Setting  ASA_PRINT_MORE  to  TRUE  will   print   out   more
intermediate  information,  e.g.,  new  parameters whenever a new
minimum is reported.  As is the case whenever  tangents  are  not
calculated   by   choosing   some   ASA   options,  normally  the
intermediate values of tangents will not be up to date.


















































                              - 14 -





Adaptive Simulated Annealing (ASA)                  Lester Ingber


7.3.  Program OPTIONS
   typedef struct {
          LONG_INT LIMIT_ACCEPTANCES;
          LONG_INT LIMIT_GENERATED;
          int LIMIT_INVALID_GENERATED_STATES;
          double ACCEPTED_TO_GENERATED_RATIO;

          double COST_PRECISION;
          int MAXIMUM_COST_REPEAT;
          int NUMBER_COST_SAMPLES;
          double TEMPERATURE_RATIO_SCALE;
          double COST_PARAMETER_SCALE;
          double TEMPERATURE_ANNEAL_SCALE;
          int USER_INITIAL_COST_TEMP;
          double *user_cost_temperature;

          int INCLUDE_INTEGER_PARAMETERS;
          int USER_INITIAL_PARAMETERS;
          ALLOC_INT SEQUENTIAL_PARAMETERS;
          double INITIAL_PARAMETER_TEMPERATURE;
          int RATIO_TEMPERATURE_SCALES;
          double *user_temperature_ratio;
          int USER_INITIAL_PARAMETERS_TEMPS;
          double *user_parameter_temperature;

          int TESTING_FREQUENCY_MODULUS;
          int ACTIVATE_REANNEAL;
          double REANNEAL_RESCALE;
          LONG_INT MAXIMUM_REANNEAL_INDEX;

          double DELTA_X;
          int DELTA_PARAMETERS;
          double *user_delta_parameter;
          int USER_TANGENTS;
          int CURVATURE_0;

          int QUENCH_PARAMETERS;
          double *user_quench_param_scale;
          int QUENCH_COST;
          double *user_quench_cost_scale;

#if OPTIONAL_DATA
          double *asa_data;
#endif
#if USER_ASA_OUT
          char *asa_out_file;
#endif
#if USER_COST_SCHEDULE
          double (*cost_schedule) ();
#endif
#if USER_REANNEAL_FUNCTION
          double (*reanneal_function) ();
#endif
#if ASA_SAMPLE



                              - 15 -





Adaptive Simulated Annealing (ASA)                  Lester Ingber


          int n_accepted;
          double bias_acceptance;
          double *bias_generated;
          double average_weights;
          double limit_weights;
#endif
#if ASA_PARALLEL
          int gener_mov_avr;
          LONG_INT gener_block;
          LONG_INT gener_block_max;
#endif
   }
USER_DEFINES;

     Note that two ways are maintained for  passing  the  Program
Options.   Check  the  comments  in  the  NOTES  file.  It may be
necessary to change some of the options for some  systems.   Read
the  NOTES  file  for some ongoing discussions and suggestions on
how to try to optimally set these options.  Note the  distinction
between  trying  to speed up annealing/quenching versus trying to
slow down annealing (which sometimes can speed up the  search  by
avoiding  spending  too much time in some local optimal regions).
Templates are set up in  ASA  to  accommodate  all  alternatives.
Below, the defaults are given in square brackets [].

(A)  user module.
     When  using  ASA  as  part  of a large library, it likely is
     easiest to make these changes within the user module,  e.g.,
     using  the  template  placed in user.c.  The Program Options
     are stored in the  structure  USER_DEFINES  *OPTIONS  (named
     USER_DEFINES *USER_OPTIONS in the user module).

(B)  asa module.
     It  likely  is most efficient to use a separate data file in
     the asa module, avoiding repeated compilations of the  code,
     to test various combinations of Program Options, e.g., using
     the file asa_opt when OPTIONS_FILE=TRUE in the  Makefile  or
     on your compilation command lines.

7.3.1.  OPTIONS->LIMIT_ACCEPTANCES[10000]

     The  maximum number of states accepted before quitting.  All
the templates in ASA have been set to use  LIMIT_ACCEPTANCES=1000
to   illustrate  the  way  these  options  can  be  changed.   If
LIMIT_ACCEPTANCES is set to 0, then no limit is  observed.   This
can be useful for some systems that cannot handle large integers.
(To exit at a  specific  number  of  generated  points,  see  the
discussion at LIMIT_INVALID_GENERATED_STATES below.)

7.3.2.  OPTIONS->LIMIT_GENERATED[99999]

     The  maximum number of states generated before quitting.  If
LIMIT_GENERATED is set to 0, then no limit is observed.  This can
be  useful  for  some  systems that cannot handle large integers.



                              - 16 -





Adaptive Simulated Annealing (ASA)                  Lester Ingber


(To exit at a  specific  number  of  generated  points,  see  the
discussion at LIMIT_INVALID_GENERATED_STATES below.)

7.3.3.  OPTIONS->LIMIT_INVALID_GENERATED_STATES[1000]

     This  sets  limits  of  repetitive invalid generated states,
e.g., when using this method to include constraints.   This  also
can  be useful to quickly exit asa() if this is requested by your
cost      function:        Setting       the       value       of
LIMIT_INVALID_GENERATED_STATES   to  0  will  exit  at  the  next
calculation of the cost  function  (possibly  after  a  few  more
exiting   calls  to  calculate  tangents  and  curvatures).   For
example, to exit asa() at a specific number of generated  points,
set  up a counter in your cost function, e.g., similar to the one
in the test function in user.c.  For all calls >=  the  limit  of
the  number  of  calls to the cost function, terminate by setting
USER_OPTIONS->LIMIT_INVALID_GENERATED_STATES  =  0  and   setting
*cost_exit  = FALSE.  (Note that the number of calls counted will
include those calls used to set up some initializations.)

7.3.4.  OPTIONS->ACCEPTED_TO_GENERATED_RATIO[1.0E-6]

     The least ratio of accepted to generated  states.   If  this
value  is  encountered,  then the usual tests, including possible
reannealing, are initiated even if the timing does  not  coincide
with  the set TESTING_FREQUENCY_MODULUS (defined below).  All the
templates     in     ASA     have     been     set     to     use
ACCEPTED_TO_GENERATED_RATIO=1.0E-4  to  illustrate  the way these
options can be changed.

7.3.5.  OPTIONS->COST_PRECISION[1.0E-18]

     This sets the precision required of  the  cost  function  if
exiting because of reaching MAXIMUM_COST_REPEAT.

7.3.6.  OPTIONS->MAXIMUM_COST_REPEAT[5]

     The  maximum  number of times that the cost function repeats
itself before quitting.

7.3.7.  OPTIONS->NUMBER_COST_SAMPLES[5]

     The number of cost function values sampled to determine  the
initial cost function temperature.

7.3.8.  OPTIONS->TEMPERATURE_RATIO_SCALE[1.0E-5]

     This scale is a guide to the expected  cost  temperature  of
convergence  within  a  small  range  of  the global minimum.  As
explained in the ASA papers, and as outlined in the  NOTES,  this
is  used  to  set  the  rates  of  annealing.   Here  is  a brief
description in terms of the temperature schedule outlined  above.





                              - 17 -





Adaptive Simulated Annealing (ASA)                  Lester Ingber


     As  a  useful  physical  guide,  the  temperature is further
parameterized in terms of quantities m_i and n_i, derived from an
"expected"  final  temperature  (which  is  not enforced in ASA),
T_fi,
        T_fi = T_0i exp(-m_i) when k_fi = exp(n_i),
        c_i = m_i exp(-n_i/D).
However, note that since the initial temperatures and  generating
indices,   T_0i  and  k_i,  are  independently  scaled  for  each
parameter, it usually is reasonable to  simply  take  {c_i,  m_i,
n_i}  to be independent of the index i, i.e., to be {c, m, n} for
all i.

     In asa.c,
        m = -log(TEMPERATURE_RATIO_SCALE).
This  can  be  overridden  if  RATIO_TEMPERATURE_SCALES  (further
discussed  below)  is set to TRUE, and then values of multipliers
of  -log(TEMPERATURE_RATIO_SCALE)  are  used  in  asa.c.    These
multipliers    are    calculated    in   the   user   module   as
USER_OPTIONS->user_temperature_ratio[]     (and     passed     to
OPTIONS->user_temperature_ratio[] in the asa module).  Then,
        m_i = m OPTIONS->user_temperature_ratio[i].

     For  large numbers of parameters, TEMPERATURE_RATIO_SCALE is
a very influential Program Option in  determining  the  scale  of
parameter  annealing.   It  likely  would be best to start with a
larger value than the default, to slow down the annealing.

7.3.9.  OPTIONS->COST_PARAMETER_SCALE[1.0]

     This  is  the  ratio of cost:parameter temperature annealing
scales.  As explained in the ASA papers, and as outlined  in  the
NOTES, this is used to set the rates of annealing.

     In  terms  of  the algebraic development given above for the
TEMPERATURE_RATIO_SCALE, in asa.c,
        c_cost = c COST_PARAMETER_SCALE.

     COST_PARAMETER_SCALE is a very influential Program Option in
determining the scale of annealing of the cost function.

7.3.10.  OPTIONS->TEMPERATURE_ANNEAL_SCALE[100.0]

     This  scale  is  a  guide  to  achieve  the  expected   cost
temperature  sought  by TEMPERATURE_RATIO_SCALE within the limits
expected by LIMIT_ACCEPTANCES.  As explained in the  ASA  papers,
and  as  outlined  in the NOTES, this is used to set the rates of
annealing.

     In terms of the algebraic development given  above  for  the
TEMPERATURE_RATIO_SCALE, in asa.c,
        n = log(TEMPERATURE_ANNEAL_SCALE).

     For  large  numbers  of parameters, TEMPERATURE_ANNEAL_SCALE
probably should at least initially be set to values greater  than



                              - 18 -





Adaptive Simulated Annealing (ASA)                  Lester Ingber


*number_parameters,  although  it  will  not be as influential as
TEMPERATURE_RATIO_SCALE.

7.3.11.  OPTIONS->USER_INITIAL_COST_TEMP[FALSE]

     Setting   USER_INITIAL_COST_TEMP  to  TRUE  permits  you  to
specify the initial cost temperature.   This  can  be  useful  in
problems  where you want to start the search at a specific scale.

7.3.12.  OPTIONS->user_cost_temperature

     If    USER_INITIAL_COST_TEMP    is    TRUE,    a    pointer,
OPTIONS->user_cost_temperature,  is used to adaptively initialize
parameters  temperatures.   If  this  choice  is  elected,   then
user_cost_temperature[]     must     be     initialized    (named
USER_OPTIONS->user_cost_temperature[] in the user  module).   (If
USER_INITIAL_COST_TEMP     is    FALSE,    then    the    pointer
*user_cost_temperature must be included in *OPTIONS, but it  need
not be initialized.)

7.3.13.  OPTIONS->INCLUDE_INTEGER_PARAMETERS[FALSE]

     Include  integer  parameters  in  derivative and reannealing
calculations.   This  is  useful  when  the  parameters  can   be
analytically  continued  between  their integer values, or if you
set the parameter increments to integral values  by  setting  the
DELTA_PARAMETERS option to TRUE, as discussed further below.

7.3.14.  OPTIONS->USER_INITIAL_PARAMETERS[FALSE]

     ASA always requests that the user guess  initial  values  of
starting  parameters,  since  that guess is as good as any random
guess the code might  make.   The  default  is  to  use  the  ASA
distribution  about  this  point  to generate an initial state of
parameters and value of the cost function that satisfy the user's
constraints.  If USER_INITIAL_PARAMETERS is set to TRUE, then the
first user's guess is used to calculate this first state.

7.3.15.  OPTIONS->SEQUENTIAL_PARAMETERS[-1]

     The ASA default for generating new points in parameter space
is to find a new point in the full space, rather than  to  sample
the  space  one  parameter at a time as do most other algorithms.
This is in accord with the general  philosophy  of  sampling  the
space  without any prior knowledge of ordering of the parameters.
However, if you have reason to believe that at some  stage(s)  of
search  there  might  be  some benefit to sampling the parameters
sequentially, then set  SEQUENTIAL_PARAMETERS  to  the  parameter
number you wish to start your annealing cycle, i.e., ranging from
0 to (*parameter_dimension - 1).  Then, ASA  will  cycle  through
your  parameters  in the order you have placed them in all arrays
defining their properties, keeping track of  which  parameter  is
actively   being   modified   in  OPTIONS->SEQUENTIAL_PARAMETERS,
thereby permitting adaptive  changes.   Any  negative  value  for



                              - 19 -





Adaptive Simulated Annealing (ASA)                  Lester Ingber


SEQUENTIAL_PARAMETERS  will  use the default ASA algorithm.  Upon
exiting asa(), SEQUENTIAL_PARAMETERS is reset back to its initial
value.

7.3.16.  OPTIONS->INITIAL_PARAMETER_TEMPERATURE[1.0]

     The   initial  temperature  for  all  parameters.   This  is
overridden by use of the  USER_INITIAL_PARAMETERS_TEMPS option.

7.3.17.  OPTIONS->RATIO_TEMPERATURE_SCALES[FALSE]

     Different  rates  of  parameter  annealing  can  be set with
RATIO_TEMPERATURE_SCALES set to TRUE.  This requires initializing
an array in the user module as discussed below.

7.3.18.  OPTIONS->user_temperature_ratio

     If    RATIO_TEMPERATURE_SCALES    is    TRUE,   a   pointer,
OPTIONS->user_temperature_ratio, is used to adaptively set ratios
of  scales  used  to  anneal the parameters in the cost function.
This can be useful when some parameters are not being reannealed,
or    when    setting    the    initial    temperatures    (using
USER_INITIAL_PARAMETERS_TEMPS set to TRUE) is not  sufficient  to
handle  all  your  parameters  properly.   This  typically is not
encountered, so it is advised  to  look  elsewhere  at  first  to
improve   your   search.    If   this  choice  is  elected,  then
user_temperature_ratio[]    must    be     initialized     (named
USER_OPTIONS->user_temperature_ratio[]  in the user module).  (If
RATIO_TEMPERATURE_SCALES   is    FALSE,    then    the    pointer
*user_temperature_ratio must be included in *OPTIONS, but it need
not be initialized.)

7.3.19.  OPTIONS->USER_INITIAL_PARAMETERS_TEMPS[FALSE]

     Setting USER_INITIAL_PARAMETERS_TEMPS to TRUE permits you to
specify  the  initial parameter temperatures.  This can be useful
in constrained problems, where greater efficiency can be achieved
in  focussing  the search than might be permitted just by setting
upper and lower bounds.

7.3.20.  OPTIONS->user_parameter_temperature

     If   USER_INITIAL_PARAMETERS_TEMPS   is   TRUE,  a  pointer,
OPTIONS->user_parameter_temperature,  is   used   to   adaptively
initialize  parameters  temperatures.  If this choice is elected,
then  user_parameter_temperature[]  must  be  initialized  (named
USER_OPTIONS->user_parameter_temperature[]  in  the user module).
(If USER_INITIAL_PARAMETERS_TEMPS  is  FALSE,  then  the  pointer
*user_parameter_temperature  must be included in *OPTIONS, but it
need not be initialized.)







                              - 20 -





Adaptive Simulated Annealing (ASA)                  Lester Ingber


7.3.21.  OPTIONS->TESTING_FREQUENCY_MODULUS[100]

     The   frequency   of   testing   for  periodic  testing  and
reannealing.

7.3.22.  OPTIONS->ACTIVATE_REANNEAL[TRUE]

     This permits reannealing to be part of the fitting  process.
This  might  have  to be set to FALSE for systems with very large
numbers of parameters just to decrease  the  number  of  function
calls.

7.3.23.  OPTIONS->REANNEAL_RESCALE[10.0]

     The  reannealing  scale  used when MAXIMUM_REANNEAL_INDEX is
exceeded.

7.3.24.  OPTIONS->MAXIMUM_REANNEAL_INDEX[50000]

     The  maximum  index  (number  of steps) at which the initial
temperature and the index of  the  temperature  are  rescaled  to
avoid   losing   machine   precision.   ASA  typically  is  quite
insensitive to the value used due to the dual rescaling.

7.3.25.  OPTIONS->DELTA_X[0.001]

     The  fractional  increment  of  parameters  used   to   take
numerical  derivatives when calculating tangents for reannealing.
This is overridden when  DELTA_PARAMETERS  is  set  to  TRUE,  as
discussed further below.

     Note  that  this can cause evaluations of your cost function
outside a  range  when  a  parameter  being  sampled  is  at  the
boundary.   However,  only values of parameters within the ranges
set by the user are actually used for acceptance tests.

7.3.26.  OPTIONS->DELTA_PARAMETERS[FALSE]

     Different increments, used during reannealing  to  set  each
parameter's    numerical    derivatives,    can   be   set   with
DELTA_PARAMETERS set to  TRUE.   This  requires  initializing  an
array in the user module as discussed below.

7.3.27.  OPTIONS->user_delta_parameter

     If      DELTA_PARAMETERS     is     TRUE,     a     pointer,
OPTIONS->user_delta_parameter,  is   used   to   adaptively   set
increments   of   parameters   used  to  take  pseudo-derivatives
(numerical derivatives).  For example,  this  can  be  useful  to
reanneal integer parameters when a choice is made to permit their
derivatives to  be  taken.   If  this  choice  is  elected,  then
OPTIONS->user_delta_parameter[]   must   be   initialized  (named
USER_OPTIONS->user_delta_parameter[] in the  user  module).   (If
DELTA_PARAMETERS is FALSE, then the pointer *user_delta_parameter



                              - 21 -





Adaptive Simulated Annealing (ASA)                  Lester Ingber


must be included in *OPTIONS, but it need not be initialized.)

7.3.28.  OPTIONS->USER_TANGENTS[FALSE]

     By  default,  asa()  calculates  numerical  tangents  (first
derivatives)  of  the cost function for use in reannealing and to
provide this information to the user.  However, if  USER_TANGENTS
is  set  to  TRUE,  then  when  asa()  requires  tangents  to  be
calculated,  a  value  of   *valid_state_generated_flag   (called
*cost_flag  in  ASA_TEST  in user.c) of FALSE is set and the cost
function is called.  The user is expected to set up a test in the
beginning  of  the  cost  function  to sense this value, and then
calculate the tangents[] array (containing the derivatives of the
cost  function,  or whatever sensitivity measure is desired to be
used for reannealing) to be returned to  asa().   An  example  is
provided with the ASA_TEMPLATE for ASA_SAMPLE.

7.3.29.  OPTIONS->CURVATURE_0[FALSE]

     If  the  curvature array is quite large for your system, and
you really do not use this information, you can  set  CURVATURE_0
to  TRUE which just requires a one-dimensional curvature[0] to be
defined to pass to the asa module (to avoid  problems  with  some
systems).   This is most useful, and typically is necessary, when
minimizing systems with large numbers  of  parameters  since  the
curvature array is of size number of parameters squared.

     If  you  wish to calculate the curvature array periodically,
every        reannealing        cycle        determined        by
OPTIONS->TESTING_FREQUENCY_MODULUS, then set OPTIONS->CURVATURE_0
to -1.

7.3.30.  OPTIONS->QUENCH_PARAMETERS[FALSE]

     This Program Option permits you to alter the basic algorithm
to   perform  selective  "quenching,"  i.e.,  faster  temperature
cooling than permitted by the ASA algorithm.  This  can  be  very
useful,  e.g.,  to  quench  the  system  down  to  some region of
interest, and then to perform proper annealing for  the  rest  of
the  run.   However,  note  that once you decide to quench rather
than  to  truly  anneal,  there  no  longer  is  any  statistical
guarantee  of  finding  a  global optimum.  Furthermore, once you
decide to quench there are many more alternative  algorithms  you
might wish to choose for your system.

     Setting QUENCH_PARAMETERS to TRUE can be extremely useful in
very large parameter dimensions.  As discussed in the first  1989
VFSR paper, the heuristic statistical proof of finding the global
optimum reduces  to  the  following:  The  parameter  temperature
schedules  must  suffice to insure that the product of individual
generating distributions,
        g = PROD_i g^i,
taken at all annealing times, indexed by k, of not  generating  a
global optimum, given infinite time, is such that



                              - 22 -





Adaptive Simulated Annealing (ASA)                  Lester Ingber


        PROD_k (1-g_k) = 0,
which is equivalent to
        SUM_k g_k = infinity.
For the ASA temperature schedule, this is satisfied as
        SUM_k PROD^D 1/k^(1/D) = SUM_k 1/k = infinity.
Now, if the temperature schedule above is redefined as
        T_i(k_i) = T_0i exp(-c_i k_i^(Q/D)),
        c_i = m_i exp(-n_i Q/D),
in  terms of the "quenching factor" Q, then the above proof fails
if Q > 1 as
        SUM_k PROD^D 1/k^(Q/D) = SUM_k 1/k^Q < infinity

     This  simple   calculation   shows   how   the   "curse   of
dimensionality"  arises,  and also gives a possible way of living
with this disease which will be present  in  any  algorithm  that
substantially samples the parameter space.  In ASA, the influence
of large dimensions becomes clearly focussed on  the  exponential
of  the  power  of  k  being  1/D,  as  the annealing required to
properly sample the space becomes prohibitively slow.  So, if  we
cannot commit resources to properly sample the space ergodically,
then for some systems perhaps the next best procedure would be to
turn  on quenching, whereby Q can become on the order of the size
of number of dimensions.  In some cases tried, a small system  of
only  a  few  parameters can be used to determine some reasonable
Program Options, and then these can be used  for  a  much  larger
space  scaled up to many parameters.  This can work in some cases
because of  the  independence  of  dimension  of  the  generating
functions.

7.3.31.  OPTIONS->user_quench_param_scale

     If     QUENCH_PARAMETERS     is     TRUE,     a     pointer,
OPTIONS->user_quench_param_scale, is used to adaptively  set  the
scale  of  the  temperature schedule.  If this choice is elected,
then  OPTIONS->user_quench_param_scale[]  must   be   initialized
(named   USER_OPTIONS->user_quench_param_scale[]   in   the  user
module),  and   values   defined   for   each   dimension.    (If
QUENCH_PARAMETERS      is     FALSE,     then     the     pointer
*user_quench_param_scale must be included  in  *OPTIONS,  but  it
need  not  be  initialized.)  The default in the asa module is to
assign the annealing value of 1 to all  elements  that  might  be
defined  otherwise.   If values are selected greater than 1 using
this Program Option, then quenching is enforced.

7.3.32.  OPTIONS->QUENCH_COST[FALSE]

     If QUENCH_COST is set to TRUE, the scale of the power of 1/D
temperature  schedule  used  for  the  acceptance function can be
altered in  a  similar  fashion  to  that  described  above  when
QUENCH_PARAMETERS is set to TRUE.  However, note that this OPTION
does not affect the annealing proof of ASA, and so this may  used
without  damaging  the  statistical  ergodicity of the algorithm.
Even greater functional changes can be made using the Pre-Compile
DEFINE_OPTIONS USER_COST_SCHEDULE.



                              - 23 -





Adaptive Simulated Annealing (ASA)                  Lester Ingber


7.3.33.  OPTIONS->user_quench_cost_scale

     If       QUENCH_COST      is      TRUE,      a      pointer,
OPTIONS->user_quench_cost_scale, is used to  adaptively  set  the
scale  of  the  temperature schedule.  If this choice is elected,
then  OPTIONS->user_quench_cost_scale[0]  must   be   initialized
(named   USER_OPTIONS->user_quench_cost_scale[0]   in   the  user
module).   (If   QUENCH_COST   is   FALSE,   then   the   pointer
*user_quench_cost_scale must be included in *OPTIONS, but it need
not be initialized.)  The default in the asa module is to  assign
the  annealing  value  of 1 to this element that might be defined
otherwise.

     OPTIONS->user_quench_cost_scale may  be  changed  adaptively
without  affecting the ergodicity of the algorithm, within reason
of course.  This might be useful for some  systems  that  require
different  approaches to the cost function in different ranges of
its parameters.  Note that increasing this parameter  beyond  its
default  of  1.0 can result in rapidly locking in the search to a
small region of the  cost  function,  severely  handicapping  the
algorithm.   On  the contrary, you may find that slowing the cost
temperature schedule, by setting this parameter to a  value  less
than 1.0, may work better for your system.

7.3.34.  OPTIONS->asa_data

     If  the  Pre-Compile  Option  OPTIONAL_DATA[FALSE] is set to
TRUE, an additional Program  Option  pointer,  OPTIONS->asa_data,
becomes available to to return additional information to the user
module from the asa module.  This information  communicates  with
the  asa  module, and memory must be allocated for it in the user
module.  An example is given  in  user.c  when  SELF_OPTIMIZE  is
TRUE.

7.3.35.  OPTIONS->asa_out_file

     If you wish to have the printing from the asa module be sent
to a file determined dynamically from the user  module,  set  the
Pre-Compile  Printing  Option  USER_ASA_OUT[FALSE]  to  TRUE, and
define the Program  Option  *asa_out_file  in  the  user  module.
(This  overrides  any  ASA_OUT settings.)  An example of this use
for multiple asa() runs is given in the user module.

7.3.36.  OPTIONS->cost_schedule

     If  USER_COST_SCHEDULE[FALSE]   is   set   to   TRUE,   then
(*cost_schedule)  ()  is  created  as  a  pointer to the function
user_cost_schedule() in user.c, and to recur_user_cost_schedule()
if SELF_OPTIMIZE is set to TRUE.

7.3.37.  OPTIONS->reanneal_function

     If   USER_REANNEAL_FUNCTION[FALSE]  is  set  to  TRUE,  then
(*reanneal_function) () is created as a pointer to  the  function



                              - 24 -





Adaptive Simulated Annealing (ASA)                  Lester Ingber


user_reanneal()   in  user.c,  and  to  recur_user_reanneal()  if
SELF_OPTIMIZE is set to TRUE.

7.3.38.  OPTIONS->n_accepted

     If ASA_SAMPLE  is  set  to  TRUE,  n_accepted  contains  the
current  number of points saved by the acceptance criteria.  This
can be used to monitor the sampling.

7.3.39.  OPTIONS->bias_acceptance

     If ASA_SAMPLE is TRUE, this is the bias of the current state
from the Boltzmann acceptance test described above.

7.3.40.  OPTIONS->bias_generated

     If  ASA_SAMPLE  is TRUE, a pointer, OPTIONS->bias_generated,
contains the the biases of the current state from the  generating
distributions   of   all   active  parameters,  described  above.
OPTIONS->bias_generated[] must be initialized in the user module.

7.3.41.  OPTIONS->average_weights

     IF  ASA_SAMPLE  is TRUE, this is the average of the weight[]
array  holding  the  products  of  the  inverse  asa   generating
distributions of all active parameters.

     For  example,  OPTIONS->n_accepted  can  be  used to monitor
changes in a new saved point  in  the  cost  function,  and  when
OPTIONS->average_weights  reaches  a  specified  number  (perhaps
repeated several  times),  the  cost  function  could  return  an
invalid  flag  from the cost function to terminate the run.  When
the average_weights is very small, then additional sampled points
likely will not substantially contribute more information.

7.3.42.  OPTIONS->limit_weights

     If  ASA_SAMPLE  is  set to TRUE, limit_weights is a limit on
the value of the  average  of  the  weight[]  array  holding  the
inverse  asa  generating  distribution.  When this lower limit is
crossed, asa will no longer send sampling output  to  be  printed
out,   although   it  still  will  be  calculated.   As  the  run
progresses, this average will decrease until  contributions  from
further sampling become relatively unimportant.

7.3.43.  OPTIONS->gener_mov_avr

     If ASA_PARALLEL is set to TRUE, gener_mov_avr determines the
window of the moving  average  of  sizes  of  parallel  generated
states  required  to find new best accepted states.  A reasonable
number for many problems is 3.

     If  and  when  OPTIONS->gener_mov_avr  is  set  to  0,  then
OPTIONS->gener_block is not changed thereafter.



                              - 25 -





Adaptive Simulated Annealing (ASA)                  Lester Ingber


7.3.44.  OPTIONS->gener_block_max

     If  ASA_PARALLEL  is  set to TRUE, gener_block is an initial
block size of parallel generated states to calculate to determine
a new best accepted state.

7.3.45.  OPTIONS->gener_block_max

     If  ASA_PARALLEL  is  set  to  TRUE,  gener_block_max  is an
initial maximum  block  size  of  parallel  generated  states  to
calculate  to  determine  a new best accepted state.  This can be
changed adaptively during the run.

     This can  be  useful  if  your  parallel  code  assigns  new
processors  "on  the  fly," to compensate for some cost functions
being more CPU intensive, e.g., due to boundary conditions,  etc.
Then  OPTIONS->gener_block_max  may  be larger than the number of
physical processors, e.g., if OPTIONS->gener_block would call for
such a size.

8.  User Module

     This  module  includes  user.c, user.h, and asa_user.h.  You
may wish to combine them into one file, or you may  wish  to  use
the ASA module as one component of a library required for a large
project.

8.1.  int main(int argc, char **argv) | int asa_main()

     In   main(),   set   up  your  initializations  and  calling
statements to asa.  The files user.c and user.h provide a  sample
program,  as well as a sample cost function for your convenience.
If you do not intend to pass parameters into main, then  you  can
just  declare  it  as main() without the argc and argv arguments,
deleting other references to argc and argv.

     If ASA_LIB is set to TRUE, then  asa_main()  is  used  as  a
function call instead of main().

     If   SELF_OPTIMIZE   is   set   to   TRUE,  then  the  first
main()/asa_main() in  user.c  is  closed  off,  and  a  different
main()/asa_main() procedure in user.c is used.

8.2.  void initialize_parameters(
          double *cost_parameters,
          double *parameter_lower_bound,
          double *parameter_upper_bound,
          double *cost_tangents,
          double *cost_curvature,
          ALLOC_INT *parameter_dimension,
          int *parameter_int_real,
          USER_DEFINES * USER_OPTIONS)





                              - 26 -





Adaptive Simulated Annealing (ASA)                  Lester Ingber


     Before  calling  asa,  the  user  must  allocate storage and
initialize some of the passed parameters.  A sample procedure  is
provided  as  a  template.   In  this  procedure  the user should
allocate storage for the passed arrays and define the minimum and
maximum  values.  Below is detailed all the parameters which must
be initialized.  If your arrays are of size 1, still use them  as
arrays as described in user.c.  Alternatively, if you define `int
user_flag', then pass &user_flag.

     As written above, these are  the  names  used  in  the  user
module.   All  these  parameters  could be passed globally in the
user module, e.g., by defining  them  in  user.h  instead  of  in
main()  in  user.c,  but  since  the asa module only passes local
parameters to facilitate recursive use, this  approach  is  taken
here as well.

8.3.  void recur_initialize_parameters(
          double *recur_cost_parameters,
          double *recur_parameter_lower_bound,
          double *recur_parameter_upper_bound,
          double *recur_cost_tangents,
          double *recur_cost_curvature,
          ALLOC_INT *recur_parameter_dimension,
          int *recur_parameter_int_real,
          USER_DEFINES * RECUR_USER_OPTIONS)

     This procedure is used only if SELF_OPTIMIZE is TRUE, and is
constructed similar to initialize_parameters().

8.4.  double user_cost_function(
          double *x,
          double *parameter_minimum,
          double *parameter_maximum,
          double *tangents,
          double *curvature,
          ALLOC_INT *number_parameters,
          int *parameter_type,
          int *valid_state_generated_flag,
          int *exit_status,
          USER_DEFINES *OPTIONS)


8.4.1.  user_cost_function

     You can give any name to user_cost_function as long  as  you
pass  this  name  to  asa; it is called cost_function in the user
module.  This function  returns  a  real  value  which  ASA  will
minimize.    In  cases  where  it  seems  that  the  ASA  default
parameters are not very efficient  for  your  system,  you  might
consider  modifying  the  cost  function  being  optimized.   For
example, if your actual cost  function  is  of  the  form  of  an
exponential  to  an  exponential,  you  might do better using the
logarithm of this as user_cost_function.




                              - 27 -





Adaptive Simulated Annealing (ASA)                  Lester Ingber


8.4.2.  *x

     x (called cost_parameters in the user module) is an array of
doubles representing a set of parameters to evaluate.

8.4.3.  double *parameter_minimum


8.4.4.  double *parameter_maximum

     These  two  arrays  of  doubles are passed.  Since ASA works
only on bounded search spaces, these arrays  should  contain  the
minimum  and  maximum  values  each parameter can attain.  If you
aren't sure, try a factor of  10  or  100  times  any  reasonable
values.   The  exponential  temperature annealing schedule should
quickly sharpen the search down to the most important region.

     Passing the parameter bounds in the  cost  function  permits
some   additional  adaptive  features  during  the  search.   For
example, setting the lower bound equal to the  upper  bound  will
remove  a parameter from consideration.  In the user module these
bounds are named parameter_lower_bound and parameter_upper_bound.

8.4.5.  double *tangents

     This  array  of  doubles is passed.  On return from asa this
contains the first derivatives of the cost function with  respect
to its parameters.  These can be useful for determining the value
of your fit.  In this implementation of  ASA,  the  tangents  are
used to determine the relative reannealing among parameters.

8.4.6.  double *curvature

     This  array  of doubles is passed next.  On return from asa,
for real parameters, this contains the second derivatives of  the
cost  function with respect to its parameters.  These also can be
useful for determining the value of your fit.

     When the DEFINE_OPTIONS CURVATURE_0 option is  set  to  TRUE
the  curvature calculations are bypassed.  This can be useful for
very large spaces.

8.4.7.  ALLOC_INT *number_parameters

     An integer containing the dimensionality of the state  space
is  passed  next (called parameter_dimension in the user module).
(If    you    define    `ALLOC_INT    number_parameters',    pass
&number_parameters.) The arrays x (representing cost_parameters),
parameter_lower_bound, parameter_upper_bound, cost_tangents,  and
parameter_int_real    (below)    are    to   be   of   the   size
*number_parameters.  The array curvature which may be of size the
square of *number_parameters.





                              - 28 -





Adaptive Simulated Annealing (ASA)                  Lester Ingber


8.4.8.  int *parameter_type

     This    integer    array   is   passed   next   (passed   as
parameter_int_real in the user module).   Each  element  of  this
array   (each  flag)  can  be:  REAL_TYPE  (-1)  (indicating  the
parameter is a real  value),  INTEGER_TYPE  (1)  (indicating  the
parameter  can  take  on  only  integer values), REAL_NO_REANNEAL
(-2), or INTEGER_NO_REANNEAL (2).  The latter two choices signify
that  no  derivatives  are  to  be  taken  with  respect to these
parameters.   For  example,  this  can  be  useful   to   exclude
discontinuous functions from being reannealed.

8.4.9.  *valid_state_generated_flag

     valid_state_generated_flag  is  the  address  of an integer,
named cost_flag in the  user  module.   In  user_cost_function(),
*cost_flag should be set to FALSE (0) if the parameters violate a
set of user defined constraints (e.g., as defined  by  a  set  of
boundary  conditions)  or  TRUE (1) if the parameters represent a
valid state.  If *cost_flag is returned to  asa()  as  FALSE,  no
acceptance  test  will  be  attempted,  and  a  new  set of trial
parameters will be generated.

     If  another  algorithm  suggests  a  way  of   incorporating
constraints  into  the  cost  function,  then  this modified cost
function can be used as well by ASA, or that algorithm might best
be used a front-end to ASA.

     If  OPTIONS->USER_TANGENTS[FALSE] has been set to TRUE, then
asa()   expects   the    user    to    test    the    value    of
*valid_state_generated_flag   that   enters   from   asa().    If
*valid_state_generated_flag enters with a value  of  FALSE,  then
the  user  is  expected to calculate the tangents[] array (called
cost_tangents[]  in  ASA_TEST  in  user.c)  before  exiting  that
particular  evaluation  of  the  cost  function.   An  example is
provided with the ASA_TEMPLATE for ASA_SAMPLE.

8.4.10.  int *exit_status

     The address of this integer is passed to asa.  On return  it
contains the code for the reason asa exited.
















                              - 29 -





Adaptive Simulated Annealing (ASA)                  Lester Ingber


     NORMAL_EXIT = 0.  Given the criteria set largely by the
     DEFINE_OPTIONS, the search has run its normal course.

     P_TEMP_TOO_SMALL = 1.  A parameter temperature was  too
     small  using  the  set  criteria.   Often  this  is  an
     acceptable status code.  You  can  omit  this  test  by
     setting  NO_PARAM_TEMP_TEST to TRUE as one of your Pre-
     Compile  Options;  then   values   of   the   parameter
     temperatures   less   than   EPS_DOUBLE   are   set  to
     EPS_DOUBLE.

     C_TEMP_TOO_SMALL = 2.  The  cost  temperature  was  too
     small  using  the  set  criteria.   Often  this  is  an
     acceptable status code.  You  can  omit  this  test  by
     setting  NO_COST_TEMP_TEST  to TRUE as one of your Pre-
     Compile Options; then a value of the  cost  temperature
     less than EPS_DOUBLE is set to EPS_DOUBLE.

     COST_REPEATING = 3.  The cost function value repeated a
     number of times using the set criteria.  Often this  is
     an acceptable status code.

     TOO_MANY_INVALID_STATES   =  4.   Too  many  repetitive
     generated states were invalid using the  set  criteria.
     This  is  helpful  when  using *cost_flag, as discussed
     above, to include constraints.

     An exit code of 9, defined by exit(9), has been set in  case
any  of  the  calloc  memory  allocations  fails.  Note that just
relying on such a simple summary given  by  *exit_status  can  be
extremely deceptive, especially in highly nonlinear problems.  It
is strongly suggested that the user set ASA_PRINT=TRUE before any
production  runs.   An examination of some periodic output of ASA
can be essential to its proper use.

8.4.11.  USER_DEFINES *OPTIONS

     All Program Options are defined in  this  structure.   Since
Program  Options  are  passed to asa and the cost function, these
may be changed adaptively.

     The Program Options also can be read in from a separate data
file,  asa_opt,  permitting  efficient  tuning/debugging of these
parameters without having to recompile the code.  This option has
been added to the asa module.












                              - 30 -





Adaptive Simulated Annealing (ASA)                  Lester Ingber


8.5.  double recur_cost_function(
          double *recur_cost_parameters,
          double *recur_parameter_lower_bound,
          double *recur_parameter_upper_bound,
          double *recur_cost_tangents,
          double *recur_cost_curvature,
          int *recur_parameter_dimension,
          int *recur_parameter_int_real,
          int *recur_cost_flag,
          int *recur_exit_code,
          USER_DEFINES * RECUR_USER_OPTIONS)

     This procedure is used only if SELF_OPTIMIZE is TRUE, and is
constructed similar to cost_function().

8.6.  double user_random_generator()

     A random number generator function must be selected.  It may
be as simple as one of the UNIX(R) random number generators (e.g.
drand48), or may be user defined, but it  should  return  a  real
value  within  [0,1)  and not take any parameters.  A good random
number  generator,  randflt,  and  its  auxiliary  routines   are
provided with the code in the user module.

8.7.  void initialize_rng()

     Most  random  number  generators  should  be  "warmed-up" by
calling a set of dummy random numbers.

8.8.  double user_cost_schedule(
          double test_temperature,
          USER_DEFINES * USER_OPTIONS);

     If USER_COST_SCHEDULE[FALSE]  is  set  to  TRUE,  then  this
function  must  define how the new cost temperature is calculated
during  the  acceptance  test.   The   default   is   to   return
test_temperature.   For  example, if you sense that the search is
spending too much time in local minima at some stage  of  search,
e.g., dependent on information gathered in USER_OPTIONS, then you
might return the square root of test_temperature, or  some  other
function,  to  slow  down  the  sharpening  of  the cost function
acceptance test.

8.9.  double recur_user_cost_schedule(
          double test_temperature,
          USER_DEFINES * RECUR_USER_OPTIONS);

     If USER_COST_SCHEDULE[FALSE] and  SELF_OPTIMIZE[FALSE]  both
are  set to TRUE, then this function must define how the new cost
temperature  is  calculated  during  the  acceptance  test.    As
discussed  above  for  user_cost_schedule(),  you  may modify the
default value of  test_temperature  returned  by  this  function,
e.g., dependent on information gathered in RECUR_USER_OPTIONS.




                              - 31 -





Adaptive Simulated Annealing (ASA)                  Lester Ingber


8.10.  double user_reanneal(
          double current_temp,
          double tangent,
          double max_tangent,
          USER_DEFINES * USER_OPTIONS);

     If  USER_REANNEAL_FUNCTION[FALSE]  is set to TRUE, then this
function must define how the new temperature is calculated during
reannealing.

8.11.  double recur_user_reanneal(
          double current_temp,
          double tangent,
          double max_tangent,
          USER_DEFINES * RECUR_USER_OPTIONS);

     If  USER_REANNEAL_FUNCTION[FALSE]  and  SELF_OPTIMIZE[FALSE]
both are set to TRUE, then this function must define how the  new
temperature is calculated during reannealing.

8.12.  final_cost = asa(
          cost_function,
          randflt,
          cost_parameters,
          parameter_lower_bound,
          parameter_upper_bound,
          cost_tangents,
          cost_curvature,
          parameter_dimension,
          parameter_int_real,
          cost_flag,
          exit_code,
          USER_OPTIONS);

     This  is  the form of the call to asa from user.c.  A double
is returned to the calling program as whatever it is named by the
user,  e.g., final_cost.  It will be the minimum cost value found
by asa.



















                              - 32 -





Adaptive Simulated Annealing (ASA)                  Lester Ingber


8.13.  double asa(
          double (*user_cost_function) (
               double *, double *, double *, double *, double *,
               ALLOC_INT *, int *, int *, int *, USER_DEFINES *),
          double (*user_random_generator) (void),
          double *parameter_initial_final,
          double *parameter_minimum,
          double *parameter_maximum,
          double *tangents,
          double *curvature,
          ALLOC_INT *number_parameters,
          int *parameter_type,
          int *valid_state_generated_flag,
          int *exit_status,
          USER_DEFINES * OPTIONS)

     This is how asa is defined in the ASA module,  contained  in
asa.c   and   asa_user.h.    All   but   the  user_cost_function,
user_random_generator,  and  parameter_initial_final   parameters
have   been   described   above   as  they  also  are  passed  by
user_cost_function().

8.13.1.  double (*user_cost_function) ()

     The parameter (*user_cost_function*) () is a pointer to  the
cost function that you defined in your user module.

8.13.2.  double (*user_random_generator) ()

     A pointer to the random number generator  function,  defined
in the user module, must be passed next.

8.13.3.  double *parameter_initial_final

     An  array of doubles is passed (passed as cost_parameters in
the user  module).   Initially,  this  array  holds  the  set  of
starting  parameters  which  should  satisfy  any  constraints or
boundary conditions.  Upon return from  the  asa  procedure,  the
array  will  contain  the  best set of parameters found by asa to
minimize the user's cost function.   Experience  shows  that  any
guesses  within  the  acceptable  ranges  should  suffice,  since
initially the system is at high  annealing  temperature  and  ASA
samples  the  breadth  of the ranges.  The default is to have asa
generate a  set  of  initial  parameters  satisfying  the  user's
constraints.       This      can      be     overridden     using
USER_INITIAL_PARAMETERS=TRUE, to have the user's initial guess be
the first generated set of parameters.

8.14.  void print_time(char *message, FILE * ptr_out)

     As a convenience, this subroutine and its auxiliary  routine
aux_print_time  are  provided  in asa.c to keep track of the time
spent during optimization.  Templates in the code are provided to
use  these routines to print to output from both the asa and user



                              - 33 -





Adaptive Simulated Annealing (ASA)                  Lester Ingber


modules.  These routines can give some  compilation  problems  on
some   platforms,   and   may   be  bypassed  using  one  of  the
DEFINE_OPTIONS.  It takes as its parameters a string  which  will
be  printed  and  the  pointer  to  file to where the printout is
directed.   An  example  is  given   in   user_cost_function   to
illustrate  how  print_time  may be called periodically every set
number of calls by defining PRINT_FREQUENCY in user.h.   See  the
NOTES  file for changes in these routines that may be required on
some particular systems.

8.15.  void sample(FILE * ptr_out, FILE * ptr_asa)

     When ASA_TEMPLATE and ASA_SAMPLE are set to true, using data
collected in the ASA_OUT file, this routine  illustrates  how  to
extract  the  data stored in the ASA_OUT file and print it to the
user module.

9.  Bug Reports

     I volunteer my time  to  make  every  reasonable  effort  to
maintain  only  current versions of the asa module, to permit the
code to compile without "error," not necessarily without compiler
"warnings."   The  user  module  is  offered  only  as a guide to
accessing the asa module.  The NOTES file  will  contain  updates
for  some  standard  machines.   I  welcome  your bug reports and
constructive critiques regarding this code.  If  you  are  having
problems,  it  might  help  if you enclose relevant portions your
ASA_OUT file.

     "Flames" will be rapidly quenched.



























                              - 34 -





Adaptive Simulated Annealing (ASA)                  Lester Ingber


10.  References

[1]  L.   Ingber,   "Adaptive   Simulated    Annealing    (ASA),"
     [ftp.alumni.caltech.edu:  /pub/ingber/ASA-shar,  ASA-shar.Z,
     ASA.tar.Z, ASA.tar.gz,  ASA.zip],  Lester  Ingber  Research,
     McLean, VA (1993).

[2]  L.   Ingber,  "Very  fast  simulated  re-annealing,"  Mathl.
     Comput. Modelling, 12, pp. 967-973 (1989).

[3]  L.  Ingber,  H.  Fujio,  and  M.F.   Wehner,   "Mathematical
     comparison  of  combat  computer  models  to exercise data,"
     Mathl. Comput. Modelling, 15, pp. 65-90 (1991).

[4]  L. Ingber, "Statistical mechanical aids to calculating  term
     structure models," Phys. Rev. A, 42, pp. 7057-7064 (1990).

[5]  L.    Ingber,    "Statistical   mechanics   of   neocortical
     interactions:    A    scaling    paradigm     applied     to
     electroencephalography,"  Phys.  Rev.  A,  44, pp. 4017-4060
     (1991).

[6]  L. Ingber, "Generic  mesoscopic  neural  networks  based  on
     statistical  mechanics  of  neocortical interactions," Phys.
     Rev. A, 45, pp. R2183-R2186 (1992).

[7]  L. Ingber and B. Rosen,  "Very  Fast  Simulated  Reannealing
     (VFSR)," [ringer.cs.utsa.edu: /pub/rosen/vfsr.Z], University
     of Texas, San Antonio, TX (1992).

[8]  L. Ingber, "Simulated annealing:  Practice  versus  theory,"
     Mathl. Comput. Modelling, 18, pp. 29-57 (1993).

[9]  M.   Wofsey,   "Technology:   Shortcut   tests  validity  of
     complicated formulas," The Wall Street Journal,  CCXXII,  p.
     B1 (24 September 1993).





















                              - 35 -





Adaptive Simulated Annealing (ASA)                  Lester Ingber


                        Table of Contents

1.   GNU General Public License (GPL) . . . . . . . . . . . .   1

2.   Documentation  . . . . . . . . . . . . . . . . . . . . .   1

2.1.           Table of Contents  . . . . . . . . . . . . . .   1

2.2.           readme.ms  . . . . . . . . . . . . . . . . . .   1

2.3.           README and README+ . . . . . . . . . . . . . .   1

2.4.           asa.[13nl] Manpage . . . . . . . . . . . . . .   1

2.5.           README.ps  . . . . . . . . . . . . . . . . . .   1

2.6.           Additional Documentation . . . . . . . . . . .   2

2.7.           Parallelizing ASA and PATHINT Project
(PAPP)  . . . . . . . . . . . . . . . . . . . . . . . . . . .   2

2.8.           Additional Information . . . . . . . . . . . .   2

3.   Availability of ASA Code . . . . . . . . . . . . . . . .   2

3.1.           Caltech  . . . . . . . . . . . . . . . . . . .   2

3.2.           Electronic Mail  . . . . . . . . . . . . . . .   3

3.3.           ASA Mailing List . . . . . . . . . . . . . . .   4

4.   Background . . . . . . . . . . . . . . . . . . . . . . .   4

4.1.           Context  . . . . . . . . . . . . . . . . . . .   4

4.2.           Outline of ASA Algorithm . . . . . . . . . . .   4

4.2.1.              Generating Probability Density Func-
tion  . . . . . . . . . . . . . . . . . . . . . . . . . . . .   4

4.2.2.              Acceptance Probability Density Func-
tion  . . . . . . . . . . . . . . . . . . . . . . . . . . . .   5

4.2.3.              Reannealing Temperature Schedule  . . . .   5

4.3.           Efficiency Versus Necessity  . . . . . . . . .   5

5.   Outline of Use . . . . . . . . . . . . . . . . . . . . .   6

6.   Makefile/Compilation Procedures  . . . . . . . . . . . .   6

7.   User Options . . . . . . . . . . . . . . . . . . . . . .   7

7.1.           Pre-Compile DEFINE_OPTIONS . . . . . . . . . .   7



                              - ii -





Adaptive Simulated Annealing (ASA)                  Lester Ingber


7.1.1.              OPTIONS_FILE=TRUE . . . . . . . . . . . .   7

7.1.2.              ASA_LIB=FALSE . . . . . . . . . . . . . .   8

7.1.3.              HAVE_ANSI=TRUE  . . . . . . . . . . . . .   8

7.1.4.              IO_PROTOTYPES=TRUE  . . . . . . . . . . .   8

7.1.5.              TIME_CALC=FALSE . . . . . . . . . . . . .   8

7.1.6.              TIME_STD=FALSE  . . . . . . . . . . . . .   8

7.1.7.              INT_LONG=TRUE . . . . . . . . . . . . . .   8

7.1.8.              INT_ALLOC=FALSE . . . . . . . . . . . . .   9

7.1.9.              SMALL_FLOAT=1.0E-18 . . . . . . . . . . .   9

7.1.10.             MIN_DOUBLE=SMALL_FLOAT  . . . . . . . . .   9

7.1.11.             MAX_DOUBLE=1.0/SMALL_FLOAT  . . . . . . .   9

7.1.12.             EPS_DOUBLE=SMALL_FLOAT  . . . . . . . . .   9

7.1.13.             NO_PARAM_TEMP_TEST=FALSE  . . . . . . . .  10

7.1.14.             NO_COST_TEMP_TEST=FALSE . . . . . . . . .  10

7.1.15.             SELF_OPTIMIZE=FALSE . . . . . . . . . . .  10

7.1.16.             ASA_TEST=FALSE  . . . . . . . . . . . . .  10

7.1.17.             ASA_TEMPLATE=FALSE  . . . . . . . . . . .  11

7.1.18.             OPTIONAL_DATA=FALSE . . . . . . . . . . .  11

7.1.19.             USER_COST_SCHEDULE=FALSE  . . . . . . . .  11

7.1.20.             USER_REANNEAL_FUNCTION=FALSE  . . . . . .  11

7.1.21.             ASA_SAMPLE=FALSE  . . . . . . . . . . . .  12

7.1.22.             ASA_PARALLEL=FALSE  . . . . . . . . . . .  12

7.2.           Printing DEFINE_OPTIONS  . . . . . . . . . . .  13

7.2.1.              ASA_PRINT=TRUE  . . . . . . . . . . . . .  13

7.2.2.              ASA_OUT=\"asa_out\" . . . . . . . . . . .  13

7.2.3.              USER_ASA_OUT=FALSE  . . . . . . . . . . .  13

7.2.4.              ASA_PRINT_INTERMED=TRUE . . . . . . . . .  13




                             - iii -





Adaptive Simulated Annealing (ASA)                  Lester Ingber


7.2.5.              ASA_PRINT_MORE=FALSE  . . . . . . . . . .  14

7.3.           Program OPTIONS  . . . . . . . . . . . . . . .  14

7.3.1.              OPTIONS->LIMIT_ACCEPTANCES[10000] . . . .  16

7.3.2.              OPTIONS->LIMIT_GENERATED[99999] . . . . .  16

7.3.3.
             OPTIONS->LIMIT_INVALID_GENERATED_STATES[1000]
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  17

7.3.4.
             OPTIONS->ACCEPTED_TO_GENERATED_RATIO[1.0E-6]
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  17

7.3.5.              OPTIONS->COST_PRECISION[1.0E-18]  . . . .  17

7.3.6.              OPTIONS->MAXIMUM_COST_REPEAT[5] . . . . .  17

7.3.7.              OPTIONS->NUMBER_COST_SAMPLES[5] . . . . .  17

7.3.8.
             OPTIONS->TEMPERATURE_RATIO_SCALE[1.0E-5] . . . .  17

7.3.9.              OPTIONS->COST_PARAMETER_SCALE[1.0]  . . .  18

7.3.10.
            OPTIONS->TEMPERATURE_ANNEAL_SCALE[100.0]  . . . .  18

7.3.11.
            OPTIONS->USER_INITIAL_COST_TEMP[FALSE]  . . . . .  19

7.3.12.             OPTIONS->user_cost_temperature  . . . . .  19

7.3.13.
            OPTIONS->INCLUDE_INTEGER_PARAMETERS[FALSE]  . . .  19

7.3.14.
            OPTIONS->USER_INITIAL_PARAMETERS[FALSE] . . . . .  19

7.3.15.             OPTIONS->SEQUENTIAL_PARAMETERS[-1]  . . .  19

7.3.16.
            OPTIONS->INITIAL_PARAMETER_TEMPERATURE[1.0]
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  20

7.3.17.
            OPTIONS->RATIO_TEMPERATURE_SCALES[FALSE]  . . . .  20

7.3.18.             OPTIONS->user_temperature_ratio . . . . .  20

7.3.19.
            OPTIONS->USER_INITIAL_PARAMETERS_TEMPS[FALSE]



                              - iv -





Adaptive Simulated Annealing (ASA)                  Lester Ingber


. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  20

7.3.20.             OPTIONS->user_parameter_temperature
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  20

7.3.21.
            OPTIONS->TESTING_FREQUENCY_MODULUS[100] . . . . .  21

7.3.22.             OPTIONS->ACTIVATE_REANNEAL[TRUE]  . . . .  21

7.3.23.             OPTIONS->REANNEAL_RESCALE[10.0] . . . . .  21

7.3.24.
            OPTIONS->MAXIMUM_REANNEAL_INDEX[50000]  . . . . .  21

7.3.25.             OPTIONS->DELTA_X[0.001] . . . . . . . . .  21

7.3.26.             OPTIONS->DELTA_PARAMETERS[FALSE]  . . . .  21

7.3.27.             OPTIONS->user_delta_parameter . . . . . .  21

7.3.28.             OPTIONS->USER_TANGENTS[FALSE] . . . . . .  22

7.3.29.             OPTIONS->CURVATURE_0[FALSE] . . . . . . .  22

7.3.30.             OPTIONS->QUENCH_PARAMETERS[FALSE] . . . .  22

7.3.31.             OPTIONS->user_quench_param_scale  . . . .  23

7.3.32.             OPTIONS->QUENCH_COST[FALSE] . . . . . . .  23

7.3.33.             OPTIONS->user_quench_cost_scale . . . . .  24

7.3.34.             OPTIONS->asa_data . . . . . . . . . . . .  24

7.3.35.             OPTIONS->asa_out_file . . . . . . . . . .  24

7.3.36.             OPTIONS->cost_schedule  . . . . . . . . .  24

7.3.37.             OPTIONS->reanneal_function  . . . . . . .  24

7.3.38.             OPTIONS->n_accepted . . . . . . . . . . .  25

7.3.39.             OPTIONS->bias_acceptance  . . . . . . . .  25

7.3.40.             OPTIONS->bias_generated . . . . . . . . .  25

7.3.41.             OPTIONS->average_weights  . . . . . . . .  25

7.3.42.             OPTIONS->limit_weights  . . . . . . . . .  25

7.3.43.             OPTIONS->gener_mov_avr  . . . . . . . . .  25

7.3.44.             OPTIONS->gener_block  . . . . . . . . . .  26



                              - v -





Adaptive Simulated Annealing (ASA)                  Lester Ingber


7.3.45.             OPTIONS->gener_block_max  . . . . . . . .  26

8.   User Module  . . . . . . . . . . . . . . . . . . . . . .  26

8.1.           int main(int argc, char **argv) | int
asa_main()  . . . . . . . . . . . . . . . . . . . . . . . . .  26

8.2.           void initialize_parameters(  . . . . . . . . .  26

8.3.           void recur_initialize_parameters(  . . . . . .  27

8.4.           double user_cost_function( . . . . . . . . . .  27

8.4.1.              user_cost_function  . . . . . . . . . . .  27

8.4.2.              *x  . . . . . . . . . . . . . . . . . . .  28

8.4.3.              double *parameter_minimum . . . . . . . .  28

8.4.4.              double *parameter_maximum . . . . . . . .  28

8.4.5.              double *tangents  . . . . . . . . . . . .  28

8.4.6.              double *curvature . . . . . . . . . . . .  28

8.4.7.              ALLOC_INT *number_parameters  . . . . . .  28

8.4.8.              int *parameter_type . . . . . . . . . . .  29

8.4.9.              *valid_state_generated_flag . . . . . . .  29

8.4.10.             int *exit_status  . . . . . . . . . . . .  29

8.4.11.             USER_DEFINES *OPTIONS . . . . . . . . . .  30

8.5.           double recur_cost_function(  . . . . . . . . .  30

8.6.           double user_random_generator() . . . . . . . .  31

8.7.           void initialize_rng()  . . . . . . . . . . . .  31

8.8.           double user_cost_schedule( . . . . . . . . . .  31

8.9.           double recur_user_cost_schedule( . . . . . . .  31

8.10.          double user_reanneal(  . . . . . . . . . . . .  31

8.11.          double recur_user_reanneal(  . . . . . . . . .  32

8.12.          final_cost = asa(  . . . . . . . . . . . . . .  32

8.13.          double asa(  . . . . . . . . . . . . . . . . .  32

8.13.1.             double (*user_cost_function) () . . . . .  33



                              - vi -





Adaptive Simulated Annealing (ASA)                  Lester Ingber


8.13.2.             double (*user_random_generator) ()  . . .  33

8.13.3.             double *parameter_initial_final . . . . .  33

8.14.          void print_time(char *message, FILE *
ptr_out)  . . . . . . . . . . . . . . . . . . . . . . . . . .  33

8.15.          void sample(FILE * ptr_out, FILE *
ptr_asa)  . . . . . . . . . . . . . . . . . . . . . . . . . .  34

9.   Bug Reports  . . . . . . . . . . . . . . . . . . . . . .  34

10.  References . . . . . . . . . . . . . . . . . . . . . . .  34


$Id: readme.ms,v 4.2 1994/10/23 23:35:08 ingber Exp ingber $









































                             - vii -